package com.zhanghp.class03;

import com.zhanghp.refer.ListNode;

import static com.zhanghp.refer.ListNode.generateRandomLinkedList;
import static com.zhanghp.refer.ListNode.printLinkedList;

/**
 * <h1>自研（参考左神思路）</h1>
 * <p>左神以下一组头节点是否存在判断</p>
 * <p>我使用第一组尾节点判断</p>
 * <p>大部分比左神的空间占用多了1M，但时间上超越了100%</p>
 *
 * @author zhanghp
 * @since 2023/10/19 11:12
 */
public class Code04_ReverseNodesInKGroup2 {
    public static void main(String[] args) {
        // 生成节点
        ListNode node = generateRandomLinkedList(3, 10);
        ListNode.printLinkedList(node);
        // 实现
        ListNode handle = reverseKGroup(node, 3);
        printLinkedList(handle);
    }

    public static ListNode reverseKGroup(ListNode head, int k){
        // 组内头节点
        ListNode start = head;
        // 上一组尾节点
        ListNode lastEnd = null;
        // 下一组尾节点
        ListNode end = getKGroupEnd(head, k);
        // 若下一组为空，则直接返回头
        if (end == null) {
            return head;
        }
        head = end;
        while (end != null) {
            // 反转
            reverse(start, k);
            if (lastEnd != null) {
                lastEnd.next = end;
            }
            // 尾节点赋值当前组头节点
            lastEnd = start;
            // 头节点赋值下一组头节点
            start = start.next;
            // 获取下一组尾节点
            end = getKGroupEnd(start, k);
            // 针对下一组不满足k大小时逻辑处理
            // 若下一组不存在，则不处理，因为上面laseEnd.next = end 处理过了
            if (end == null && start != null) {
                lastEnd.next = start;
                return head;
            }
        }
        return head;

    }


    public static void reverse(ListNode head, int k) {
        ListNode pre = null;
        ListNode next = null;
        ListNode start = head;
        while (--k >= 0 && head != null) {
            next = head.next;
            head.next = pre;
            pre = head;
            head = next;
        }
        start.next = head;
    }

    public static ListNode getKGroupEnd(ListNode head, int k){
        while (--k != 0 && head != null) {
            head = head.next;
        }
        return head;
    }

}
